#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

#define Max 100
#define RAND_MAX 100

void RandomGenerateMaTrix(int a[Max][Max], int n);
void PrintMatrix(int a[Max][Max], int n);
int random_in_range (unsigned int min, unsigned int max);


int random_in_range (unsigned int min, unsigned int max)
{
  //Randomize
  int base_random = rand(); /* in [0, RAND_MAX] */
  if (RAND_MAX == base_random) return random_in_range(min, max);
  /* now guaranteed to be in [0, RAND_MAX) */
  int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;
  /* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void RandomGenerateMatrix(int a[Max][Max], int n)
{
	for(int i = 0; i < n; i++)
	{
		for	(int j = 0; j < n; j++)
		{
			if(i==j)
			{
				a[i][j] = 0;	
			}
			else
			
			a[i][j] = random_in_range(1,10);	
		}
	}
}

void PrintMatrix(int a[Max][Max], int n)
{
	for(int i = 0; i < n; i++)
	{
		for	(int j = 0; j < n; j++)
		{
			printf("  %d",a[i][j]);	
		}
		printf("\n\n");
	}
}

int main () {
	
	int TotalCost = 0;//Luu lai tong chi phi cua mot chu trinh
	int LastCity;//Luu lai thanh pho cuoi cung duoc ghe tham, truoc khi tro ve thanh pho 1
	int MaTrixForCitiesDistances[Max][Max]; //Ma tran lu lai chi phi duong di giua cac thanh php	
	int NumberOfCity = 4; //Tong so thanh pho 	
	int TravelPath[Max];  //Luu mot chu trinh travel
	int MinCost = std::numeric_limits<int>::max(); //Ket qua: chi phi thap nhat
	
	//printf("%d\n",MinCost);
	//printf("\n");
	RandomGenerateMatrix(MaTrixForCitisDistances,NumberOfCity);	                        
	PrintMatrix(MaTrixForCitiesDistances,NumberOfCity);	                                
	for(int i = 0; i < NumberOfCity-1; i++)                                             
	{                                                                                   
		TravelPath[i] = i+2;	                                                              
	}                                                                                   
	/*/                                                                                 
	for(int i = 0; i < NumberOfCity - 1; i++)                                           
	{                                                                                   
		printf("  %d", TravelPath[i]);                                                     
	}                                                                                   
	/*/                                                                                 
	printf("\n\n");                                                                     
	//                                                                                  
  	//int myints[] = {2,3,4,5};                                                       
	//int n =4;                                                                         
  	                                                                                  
  	//sort (TravelPath,TravelPath+NumberOfCity-1);                                    
  	do {                                                                              
  		TotalCost = 0;                                                                   
  		printf(" 1");                                                                    
	  	for(int i = 0; i< NumberOfCity-1; i++)                                           
	  	{                                                                                
	  		                                                                                
	  		TotalCost += MaTrixForCitiesDistances[TravelPath[i]-1-1][TravelPath[i]-1];      
	  		printf("  <%d> ", MaTrixForCitiesDistances[TravelPath[i]-1-1][TravelPath[i]-1] );
	  		printf("  %d", TravelPath[i]);                                                  
	  		LastCity = i;                                                                   
	  	}                                                                                
	  	printf("  <%d>  1", MaTrixForCitiesDistances[TravelPath[LastCity]-1][0]);        
	  	TotalCost += MaTrixForCitiesDistances[TravelPath[LastCity]-1][0];                
		printf(" -> %d\n", TotalCost);                                                     
		if(MinCost>TotalCost)                                                              
		{                                                                                  
			MinCost = TotalCost;	                                                             
		}                                                                                  
		                                                                                   
	    //cout << myints[0] << " " << myints[1] << " " << myints[2] << " " << myints[3] <<endl;
  	} while ( next_permutation (TravelPath,TravelPath+NumberOfCity-1) );              
  	//} while ( next_permutation (myints,myints+n) );                                 
	printf("\n\n<<%d>>\n\n", MinCost);                                                  
  	return 0;                                                                         
}